package yao.xerophyte.java.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序
 *
 * @author yaojx
 */
public class Selection {
    
    public static void main(String[] args) {
        int length = 10000;
        int[] sortArray1 = generateRandomArr(length);
        int[] sortArray1Check = new int[sortArray1.length];
        System.arraycopy(sortArray1, 0, sortArray1Check, 0, sortArray1.length);
        Arrays.sort(sortArray1Check);
        System.out.println("==============基础实现选择排序：");
        selectionSortBase(sortArray1);
        System.out.println("排序结果是否正确：" + check(sortArray1, sortArray1Check));
        
        int[] sortArray2 = generateRandomArr(length);
        int[] sortArray2Check = new int[sortArray2.length];
        System.arraycopy(sortArray2, 0, sortArray2Check, 0, sortArray2.length);
        Arrays.sort(sortArray2Check);
        System.out.println("==============优化后的选择排序：");
        selectionSortOptimization(sortArray2);
        System.out.println("排序结果是否正确：" + check(sortArray2, sortArray2Check));
    }
    
    /**
     * 基础实现
     *
     * @param sortArray 要排序的数组
     */
    private static void selectionSortBase(int[] sortArray) {
        int count = 0;
        for (int sortedIndex = 0; sortedIndex < sortArray.length - 1; sortedIndex++) {
            int minIndex = sortedIndex;
            for (int currentIndex = sortedIndex + 1; currentIndex < sortArray.length; currentIndex++) {
                if (sortArray[currentIndex] < sortArray[minIndex]) {
                    minIndex = currentIndex;
                }
                count++;
            }
            changePosition(sortArray, sortedIndex, minIndex);
        }
        System.out.println("循环次数：" + count);
    }
    
    /**
     * 优化版选择排序
     *
     * <p>优化点：
     * <p>1、找最小值的时候可以同时找最大值
     * <p>2、找最大最小值的时候可以一下找两个
     *
     * @param sortArray 要排序的数组
     */
    private static void selectionSortOptimization(int[] sortArray) {
        int count = 0;
        int lastIndex = sortArray.length - 1;
        for (int sortedIndex = 0; sortedIndex <= lastIndex - sortedIndex; sortedIndex++) {
            int minIndex = sortedIndex;
            int maxIndex = lastIndex - sortedIndex;
            for (int currentIndex = sortedIndex + 1; currentIndex <= lastIndex - sortedIndex; currentIndex += 2) {
                
                int tempMinIndex = currentIndex;
                int tempMaxIndex = currentIndex + 1;
                if (currentIndex != lastIndex - sortedIndex && currentIndex + 1 < sortArray.length) {
                    if (sortArray[currentIndex] > sortArray[currentIndex + 1]) {
                        tempMinIndex = currentIndex + 1;
                        tempMaxIndex = currentIndex;
                    }
                } else {
                    tempMaxIndex = currentIndex;
                }
                if (sortArray[tempMinIndex] < sortArray[minIndex]) {
                    minIndex = tempMinIndex;
                }
                if (sortArray[tempMaxIndex] > sortArray[maxIndex]) {
                    maxIndex = tempMaxIndex;
                }
                if (sortArray[sortedIndex] > sortArray[maxIndex]) {
                    maxIndex = sortedIndex;
                }
                count++;
            }
            if (maxIndex == sortedIndex) {
                if (minIndex == lastIndex - sortedIndex) {
                    changePosition(sortArray, lastIndex - sortedIndex, maxIndex);
                } else {
                    changePosition(sortArray, lastIndex - sortedIndex, maxIndex);
                    changePosition(sortArray, sortedIndex, minIndex);
                }
            } else {
                changePosition(sortArray, sortedIndex, minIndex);
                changePosition(sortArray, lastIndex - sortedIndex, maxIndex);
            }
        }
        System.out.println("循环次数：" + count);
    }
    
    /**
     * 生产随机样本
     *
     * @param length 指定数组长度
     * @return 指定长度的数组样本
     */
    private static int[] generateRandomArr(int length) {
        Random random = new Random();
        int[] sortArray = new int[length];
        for (int i = 0; i < sortArray.length; i++) {
            sortArray[i] = random.nextInt(length);
        }
        return sortArray;
    }
    
    /**
     * 校验两个数组是否相等
     *
     * @param sortArray1 数组1
     * @param sortArray2 数组2
     * @return 是否相等
     */
    private static boolean check(int[] sortArray1, int[] sortArray2) {
        if (sortArray1 == null || sortArray2 == null || sortArray1.length != sortArray2.length) {
            return false;
        }
        for (int i = 0; i < sortArray1.length; i++) {
            if (sortArray1[i] != sortArray2[i]) {
                System.out.println("对数错误，index=" + i);
                return false;
            }
        }
        return true;
    }
    
    /**
     * 交换数组中两个元素的位置
     *
     * @param arraySrc    需要交换的数组
     * @param firstIndex  位置1
     * @param secondIndex 位置2
     */
    private static void changePosition(int[] arraySrc, int firstIndex, int secondIndex) {
        int tempValue = arraySrc[firstIndex];
        arraySrc[firstIndex] = arraySrc[secondIndex];
        arraySrc[secondIndex] = tempValue;
    }
    
    /**
     * 打印数组
     *
     * @param arraySrc 需要打印的数组
     */
    private static void printArray(int[] arraySrc) {
        StringBuilder stringBuilder = new StringBuilder("[");
        if (arraySrc != null && arraySrc.length > 0) {
            for (int i = 0; i < arraySrc.length; i++) {
                stringBuilder.append(arraySrc[i]);
                if (i != arraySrc.length - 1) {
                    stringBuilder.append(",");
                } else {
                    stringBuilder.append("]");
                }
            }
        } else {
            stringBuilder.append("]");
        }
        System.out.println(stringBuilder.toString());
    }
}
